package com.test.daily.leetcode.y2021.m11.day1127;

import java.util.HashMap;
import java.util.Random;

/**
 * Solution
 *
 * @author Tom on 2021/11/27
 */
public class Code01_Solution {

    public int m, n, total;
    public HashMap<Integer, Integer> map = new HashMap<>();
    Random ramdom = new Random();

    public Code01_Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.total = m * n;
    }

    public int[] flip() {
        int x = ramdom.nextInt(total);
        total--;
        int idx = map.getOrDefault(x, x);
        // 1. 把二维的值映射到一维表
        // 2. 一维表的随机位置x与一维表未使用的最后一个位置k-1交换
        // 3. 下一次再随机选取时时,是从0~k-2位置选择
        // 4.1 如果随机抽取的值 为 之前已经选择的值,则取出原值
        // 4.2 如果随机抽取的值,在之前未出现过,则为原值
        map.put(x, map.getOrDefault(total, total));
        // 5. 映射回二维表
        return new int[]{idx / n, idx % n};
    }

    public void reset() {
        map.clear();
        total = m * n;
    }
}
